#include<iostream>
#include<ctime>
#include<cstdlib>
#include<cmath>
using namespace std;

bool underDiagAttack(int tCol, int aCol, int tRow, int aRow){
	if (abs(aRow - tRow) == abs(aCol - tCol))
		return 1;
	return 0;
}

int getNoOfLinks(int n)
{
	return ((n*(n - 1)) / 2);
}

int rouletteWheel(int rel[], int n, int rSum)
{
	int* wheelPartitions = new int[n-1];
	int sum = 0;
	int randomNo = (rand()%rSum)+1;
	//cout << "Random Number: " << randomNo << endl;
	for (int i = 0; i < n-1; i++)
	{
		wheelPartitions[i] = sum + rel[i];
		sum = wheelPartitions[i];
		if (randomNo <= wheelPartitions[i])
			return i;
	}
	return n-1;
}

void mutation(int**& tempChromosomes, int noOfChromosomes, int n)
{
	tempChromosomes[(rand() % noOfChromosomes)][(rand()%n)] = rand() % n;
}

void crossover(int**& tempChromosomes, int** chromosome, int* relFitness, int noOfChromosomes, int relFitSum, int n)
{
	int j;
	int firstTempIndex = 0;
	int secondTempIndex = 1;
	int cutIndex;
	int firstChrIndex;
	int secondChrIndex;
	for (int k = 0; k < (noOfChromosomes / 2); k++)
	{
		cutIndex = rand() % (n - 1);	//shift starting from value at this index
		//cout << "\nCut before: " << cutIndex + 1<<endl;
		/***********************************Select Chromosomes**********************************/
		firstChrIndex = rouletteWheel(relFitness, noOfChromosomes, relFitSum);
		//cout << "1st Selected Chromosome: c" << firstChrIndex + 1 << endl;
		secondChrIndex = rouletteWheel(relFitness, noOfChromosomes, relFitSum);
		//cout << "2nd Selected Chromosome: c" << secondChrIndex + 1 << endl << endl;

		j = cutIndex;
		for (int i = 0; i < n; i++)
		{
			if (i < cutIndex)
				tempChromosomes[firstTempIndex][i] = chromosome[firstChrIndex][i];
			else
			{
				tempChromosomes[firstTempIndex][i] = chromosome[secondChrIndex][j];
				j++;
			}
		}

		j = cutIndex; 
		for (int i = 0; i < n; i++)
		{
			if (i >= cutIndex)
			{
				tempChromosomes[secondTempIndex][i] = chromosome[firstChrIndex][j];
			j++;
			}
			else
				tempChromosomes[secondTempIndex][i] = chromosome[secondChrIndex][i];
		}
		firstTempIndex += 2;
		secondTempIndex += 2;
	}
}

void main()
{
	int** chromosome;
	srand(time(0));
	int n;	//board size n x n
	cout << "Enter board dimension: ";
	cin >> n;
	int noOfChromosomes = 4;
	chromosome = new int*[noOfChromosomes];
	int totalLinks = getNoOfLinks(n);
	int max_fitness = 0;
	int* fit_chromosome = new int[n];
	//cout << totalLinks << endl;

	/***********************************Populate Chromosomes**********************************/
	for (int i = 0; i < noOfChromosomes; i++)
	{
		chromosome[i] = new int[n];
	}
	for (int i = 0; i < noOfChromosomes; i++)
	{
		for (int j = 0; j < n; j++)
		{
			chromosome[i][j] = (rand() % n) + 1;
			//cout << chromosome[i][j] << " ";
		}
		//cout << endl;
	}
	//cout << endl;
	/***********************************Calculate Fitness**********************************/
	int failures;
	int* fitness = new int[noOfChromosomes];
	int colFailures = 0;
	int diagFailures = 0;
	int skipTill = 1;
	bool inLineColQueens = false;
	bool inLineDiagQueens = false;
	int* relFitness = new int[noOfChromosomes];
	int fitnessSum = 0;
	int counter = 1;
	for (; counter <= 100000 ; counter++)	//counter is no. of populations
	{
		//cout << "\nIteration no: " << coun.ter << endl;
		for (int chCtr = 0; chCtr < noOfChromosomes; chCtr++)
		{
			for (int attacking = 0; attacking < n; attacking++)
			{
				for (int target = skipTill; target < n; target++)
				{
					if ((chromosome[chCtr][target] == chromosome[chCtr][attacking]) && !inLineColQueens)
					{
						inLineColQueens = true;
						colFailures++;
					}
					if (underDiagAttack(chromosome[chCtr][target], chromosome[chCtr][attacking], target, attacking) && !inLineDiagQueens)
					{
						inLineDiagQueens = true;
						diagFailures++;
					}
				}
				inLineColQueens = false;
				inLineDiagQueens = false;
				skipTill++;
			}
			failures = colFailures + diagFailures;
			//cout << "Failures: " << failures << endl;
			fitness[chCtr] = totalLinks - failures;
			fitnessSum += fitness[chCtr];
			failures = 0;
			colFailures = 0;
			diagFailures = 0;
			skipTill = 1;

			/****Update Max fitness****/
			if (fitness[chCtr] > max_fitness)
			{
				max_fitness = fitness[chCtr];
				for (int copyCtr = 0; copyCtr < n; copyCtr++){
					fit_chromosome[copyCtr] = chromosome[chCtr][copyCtr];
				}
				
			}
		}
		//cout << endl;

		/***********************************Calculate Relative Fitness**********************************/
		for (int i = 0; i < noOfChromosomes; i++)
		{
			relFitness[i] = (fitness[i] * 100) / fitnessSum;
			//cout << "Fitness: " << fitness[i] << endl;
			//cout << "Fitness Sum: " << fitnessSum << endl;
			//cout << "Relative Fitness: " << relFitness[i] << endl << endl;	//Sum not 100
		}

		int relFitSum = 0;
		for (int i = 0; i < noOfChromosomes; i++)
		{
			relFitSum += relFitness[i];
		}
		//cout << "Relative Fitness Sum: " << relFitSum << endl;

		int** tempChromosomes;
		tempChromosomes = new int*[noOfChromosomes];
		for (int i = 0; i < noOfChromosomes; i++)
		{
			tempChromosomes[i] = new int[n];
		}

		crossover(tempChromosomes, chromosome, relFitness, noOfChromosomes, relFitSum, n);	//crossover, noOfChromosomes/2 time
		mutation(tempChromosomes,noOfChromosomes,n);

		///************************Find chromosomes with minimum Fitness****************************/Giving worse solution
		//int minIndex=0 ,secMinIndex;
		//int minRelFitness=100;
		//for ( int i = 0; i < noOfChromosomes; i++ )
		//{
		//	if(relFitness[i] <= minRelFitness)
		//	{
		//		secMinIndex = minIndex;
		//		
		//		minRelFitness = relFitness[i];
		//		minIndex = i;
		//	}
		//}
		//
		//chromosome[minIndex][rand()%n] = rand()%n;
		//chromosome[secMinIndex][rand()%n] = rand()%n;

		for (int i = 0; i < noOfChromosomes; i++)
		{
			for (int j = 0; j < n; j++)
			{
				chromosome[i][j] = tempChromosomes[i][j];
				//cout << tempChromosomes[i][j] << " ";
			}
			//cout << endl;
		}
		fitnessSum = 0;
		if (((max_fitness * 100) / totalLinks) == 100)
			break;
	}
	cout << "Total Iterations: " << counter - 1;
	cout << "\nMost Suitable Positions: ";
	for (int i = 0; i < n-1; i++)
	{
		cout<<fit_chromosome[i]<<",";
	}
	cout << fit_chromosome[n - 1]<<endl;
	cout << "Fitness: " << max_fitness << endl;
	cout << "Fitness Ratio: " << (max_fitness * 100) / totalLinks << endl;
}